#ifndef __LINKTREE_H_
#define __LINKTREE_H_

#include "DoubleLinkList.h"
#include <string>

class LinkTree;  //前置声明
class TreeNode  //树的节点
{
public:
    //using ElementType = int;
    //using ElementType = std::string;
    using ElementType = void*;
    
    TreeNode(const ElementType &element);
    //将一个结点绑定成另一个结点的孩子
    void Connect(TreeNode *parent);
    //解绑
    void Disconnect(TreeNode *parent);
    TreeNode * GetParent(){ return parent;}
    ElementType GetData(){ return data;}
    void SetData(const ElementType & element){ data = element;}
    friend LinkTree;  //友元类
private:
    ElementType data;  //数据域
    TreeNode *parent;  //双亲结点
    TreeNode *firstChild;  //第一个孩子结点
    TreeNode *nextSbling;  //下一个兄弟结点
};

class LinkTree
{
public:
    using ElementType = TreeNode::ElementType;
    LinkTree();
    ~LinkTree();
    TreeNode *GetRoot(){ return root;}
    void show();

    DoubleLinkList FindByElement(const ElementType &element);
    int GetTreeHeight();
    //统计树中结点数量
    int Size();
    //统计树中叶子结点数量
    int Count();

    void SetFreeFunc(void (*Free)(void *))
    {
        this->Free = Free;
    }

    void SetCompareFunc(bool (*Compare)(void *, void *))
    {
        this->Compare = Compare;
    }

    void SetPrintFunc(void (*Print)(void *))
    {
        this->Print = Print;
    }

    void SetCopyData(ElementType (*CopyData)(void *))
    {
        this->CopyData = CopyData;
    } 
private:
    int GetNodeHeight(TreeNode *node);
    void GetNodeSize(TreeNode *node, int & cout);
    void GetNodeCount(TreeNode *node, int & count);
    void FindNode(TreeNode *node, const ElementType & element, DoubleLinkList & list);
    void show(TreeNode *node,int deepth);
    void FreeNode(TreeNode *node);
    TreeNode *root;  //根节点

    void (*Free)(void *);   //释放对象
    bool (*Compare)(void *, void *);    //比较大小
    void (*Print)(void *);  //打印
    ElementType (*CopyData)(void *);   //拷贝内容
};

#endif
